package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/">从根到叶的二进制数之和(Sum of Root To Leaf Binary Numbers)</a>
 * <p>
 *     给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
 *     <ul>
 *     <li>例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。</li></ul>
 * </p>
 * <p>对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。</p>
 * <p>返回这些数字之和。题目数据保证答案是一个 32 位 整数。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,0,1,0,1,0,1]
 *      输出：22
 *      解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
 *
 * 示例 2：
 *      输入：root = [0]
 *      输出：0
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中的节点数在 [1, 1000] 范围内</li>
 *     <li>Node.val 仅为 0 或 1 </li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/20 14:55
 */
public class LC1022SumOfRootToLeafBinaryNumbers_S {

    static class Solution {

        /**
         * 层序遍历
         */
        public int sumRootToLeaf(TreeNode root) {
            int sum = 0;
            Queue<TreeNode> queue = new ArrayDeque<>();
            queue.offer(root);
            while ( !queue.isEmpty()) {
                // 层序遍历
                int currLevelNodeSize = queue.size();
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = queue.poll();
                    // 如果是叶子节点
                    if (currNode.left == null && currNode.right == null) {
                        sum += currNode.val;
                    }
                    if (currNode.left != null) {
                        currNode.left.val |= currNode.val << 1;
                        queue.offer(currNode.left);
                    }
                    if (currNode.right != null) {
                        currNode.right.val |= currNode.val << 1;
                        queue.offer(currNode.right);
                    }
                }
            }
            return sum;
        }



        public int sumRootToLeaf2(TreeNode root) {
            return dfs(root, 0);
        }

        private int dfs(TreeNode currNode, int parentNodeVal) {
            if (currNode == null) {
                return 0;
            }
            // 父节点的val<<1 | 当前节点的val。作为当前节点的值
            int currNodeVal = parentNodeVal << 1 | currNode.val;
            // 当前节点为叶子节点
            if (currNode.left == null && currNode.right == null) {
                return currNodeVal;
            }
            // 当前节点的值，作为子节点的父节点的父节点的值，进行递归
            return dfs(currNode.left, currNodeVal) + dfs(currNode.right, currNodeVal);
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        TreeNode root2 = new TreeNode(0);
        TreeNode root3 = new TreeNode(1);
        root3.left = new TreeNode(0);
        root3.right = new TreeNode(1);
        root3.left.left = new TreeNode(0);
        root3.left.right = new TreeNode(1);
        root3.right.left = new TreeNode(0);
        root3.right.right = new TreeNode(1);
        Solution solution = new Solution();
        //System.out.println(solution.sumRootToLeaf(root1));
        System.out.println(solution.sumRootToLeaf(root2));
        System.out.println(solution.sumRootToLeaf(root3));
    }
}
